package top.humbleyuan.stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 21:52
 * @Des 最大矩形,类比84
 * @pro 待补充dp解法
 */
public class LeetCode_85 {
    public static void main(String[] args) {
        /**
         * 1. 从上往下进行每一行的遍历；
         * 2. 用一个数组记录每一列的高度，当前节点为0时高度直接为0，若当前节点非0则+1；
         * 3. 对每一行计算最大矩形
         */
        char[][] nums = {
                {'1','0','1','0','0'},
                {'1','0','1','1','1'},
                {'1','1','1','1','1'},
                {'1','0','0','1','0'}};

        int[] heights = new int[nums[0].length];

        int maxArea = 0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[i].length; j++) {
                if(nums[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }

            maxArea = Math.max(maxArea, singleRec(heights));
        }

        System.out.println(maxArea);
    }

    public static int singleRec(int[] heights) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        int maxArea = 0;

        for (int i = 0; i < heights.length; i++) {

            while (stack.peek() != -1 && heights[stack.peek()] > heights[i]) {
                int index = stack.poll();

                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, width * heights[index]);
            }

            stack.push(i);
        }

        while (stack.peek() != -1) {
            int index = stack.poll();

            int width = heights.length - stack.peek() - 1;
            maxArea = Math.max(maxArea, width * heights[index]);
        }

        return maxArea;
    }
}
